|
In graph theory, Grinberg's theorem is a necessary condition for a planar graph to contain a Hamiltonian cycle, based on the lengths of its face cycles. The result has been widely used to construct non-Hamiltonian planar graphs with further properties, such as to give new counterexamples to Tait's conjecture (originally disproved by W.T. Tutte in 1946). This theorem was proved by Latvian mathematician Emanuel Grinberg in 1968. == Formulation == Let ''G'' be a finite planar graph with a Hamiltonian cycle ''C'', with a fixed planar embedding. Denote by ''ƒ''''k'' and ''g''''k'' the number of ''k''-gonal faces of the embedding that are inside and outside of ''C'', respectively. Then : The proof is an easy consequence of Euler's formula. A corollary of this theorem is that if a planar graph can be embedded in such a way that all but one face has a number of sides that is 2 mod 3, and the remaining face has a number of sides that is not 2 mod 3, then the graph is not Hamiltonian. For instance, for the graph in the figure, all the bounded faces have 5 or 8 sides, but the unbounded face has 9 sides, so it satisfies this condition and is not Hamiltonian. For any planar graph, the faces whose number of sides is 2 mod 3 contribute 0 mod 3 to the sum in Grinberg's theorem, because of the factor of ''k'' − 2 in the sum. However, the other faces contribute a number that nonzero mod 3, regardless of whether they are inside or outside the Hamiltonian cycle. So, when there is only one face that contributes a nonzero amount, it is not possible for the total to be zero and the graph must be non-Hamiltonian. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Grinberg's theorem」の詳細全文を読む スポンサード リンク
|